package nowCoder;

/**
 * Created by Ghost on 2015/1/27 0027.
 */
public class MaxSumSubTree {
    class TreeNode{
        TreeNode left,right;
        int tag;
        TreeNode(int tag){
            this.tag = tag;
        }
    }

    private TreeNode maxRoot = new TreeNode(0);
    public int find(TreeNode root){
        if(root==null){
            return 0;
        } else{
            int lSum = find(root.left);
            int rSum = find(root.right);
            if(maxRoot.tag<lSum)
                maxRoot = root.left;
            if(maxRoot.tag<rSum)
                maxRoot = root.right;
            return root.tag+lSum+rSum;
        }
    }
}
